#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
  struct ListNode {
      int val;
    ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

  ListNode* mergeTwoLists(ListNode*a,ListNode*b){
      ListNode*head;
      if(a== nullptr)return b;
      if(b== nullptr)return a;
      if(a->val<b->val){
          head=a;
          head->next=mergeTwoLists(a->next,b);
      }else {
          head=b;
          head->next=mergeTwoLists(a,b->next);
      }
      return head;
  }

ListNode* mergeKLists(vector<ListNode*>& lists) {
      if(lists.size()==0) return nullptr;
    if(lists.size()==1) return lists[0];
    if(lists.size()==2)return mergeTwoLists(lists[0],lists[1]);
    vector<ListNode*>l1;
    short size=lists.size();
    short mid=size/2;
    for(short i=0;i<mid;i++){
        l1.push_back(lists[i]);
    }
    vector<ListNode*>l2;
    for(short i=mid;i<size;i++){
        l2.push_back(lists[i]);
    }
    return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
}

int main(){
    ListNode* temp;
    ListNode* a1=new ListNode(1);
    temp=a1;
    temp->next=new ListNode(4);
    temp=a1->next;
    temp->next=new ListNode(5);

    ListNode* a2=new ListNode(1);
    temp=a2;
    temp->next=new ListNode(3);
    temp=temp->next;
    temp->next=new ListNode(4);

    ListNode* a3=new ListNode(2);
    temp=a3;
    temp->next=new ListNode(6);

    vector<ListNode*>a={a1,a2,a3};

//    mergeKLists(a);
//    ListNode*result=mergeTwoLists(a1,a2);
    ListNode*result=mergeKLists(a);
    while(result!= nullptr){
        cout<<result->val<<",";
        result=result->next;
    }
    return 0;
}